package binarySearch;

public class searchRange {
    public int[] searchRange(int[] nums, int target) {
        int left = binarySearch(nums, target, true);   
        int right = binarySearch(nums, target, false)-1;
        if (left>=0&&right<nums.length&&left<=right&&nums[left]==target&&nums[right]==target) {
            return new int[]{left,right};
        }   
        return new int[]{-1,-1};
    }

    public int binarySearch(int[] nums, int target,boolean lower) {
        int left=0,right=nums.length-1;
        int mid =0,ans=nums.length;
        while (left<=right) {
            //可能越界
            mid=(left+right)/2;
            if (nums[mid]>target||(lower&&nums[mid]>=target)) {
                //lower为true表明，当找到时，会去找找有没有值相同，index更小的，从而找到index最小的
                right=mid-1;
                //相当于是留个保底，免得待会过了，找不到了
                ans=mid;
            }else{
                //lower为false表明，对于那些相同的值，index++，从而找到第一个比他大的
                left=mid+1;
            }

        }
        return ans;
        

    }

    public static void main(String[] args) {
        searchRange obj = new searchRange();
        int[] nums = new int[]{5,7,7,7,7,7,8,8,9,9,9,9,10,10};
        //你找-1 +1 可能也有重复
        int[] rs = obj.searchRange(nums, 8);
        System.out.println(rs[0]);
        System.out.println("=========");
        System.out.println(rs[1]);
    }
}
